package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-07 16:26
 */
public class GenerateParenthesis2 {


    public static void main(String[] args) {
        //先找出共有多少种组合 再遍历组合将其变成括号
        List<String> strings3 = generateParenthesis2(4);
        System.out.println(strings3);
    }


    // 其实考的就是 n 有多少种组合 再将组合变换成具体字符即可
    public static List<String> generateParenthesis2(int n) {
        List<String> list = new ArrayList<>();
        if (n == 1) {
            list.add("1");
            return list;
        }
        list.add(n + "");
        for (int i = 1; i < n; i++) {
            List<String> strings = generateParenthesis2(i);
            for (int j = 0; j < strings.size(); j++) {
                list.add(strings.get(j) + " " + (n - i));
            }
        }
        return list;
    }

    // 其实考的就是 n 有多少种组合 再将组合变换成具体字符即可
    public static List<String> generateParenthesis3(int n) {
        List<String> list = new ArrayList<>();
        if (n == 1) {
            list.add(")");
            return list;
        }
        list.add(getBrackets(n));
        for (int i = 1; i < n; i++) {
            List<String> strings = generateParenthesis3(i);
            for (int j = 0; j < strings.size(); j++) {
                list.add(strings.get(j) + "(" + getBrackets(n - i));
            }
        }
        return list;
    }

    private static String getBrackets(int n) {
        String ss = "";
        for (int i = 0; i < n; i++) {
            ss += ")";
        }
        return ss;
    }

}
